package src.leetcode.hot.hard_0030;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class findSubstring {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"}));
    }
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> nums = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        int n = words.length, slen = s.length();
        String sign = words[0] + " ";
        map.put(sign, 0);
        for (String word : words) {
            map.put(word, 0);
            nums.put(word, nums.getOrDefault(word, 0) + 1);
        }


        int step = words[0].length();
        for (int i = 0; i < step; i++) {
            for(String key : map.keySet()){
                map.put(key, 0);
            }
            int fast = i, slow = i;
            while (fast + step <= slen) {
                String ts = s.substring(fast, fast + step);
                if (map.containsKey(ts)) {
                    map.put(ts, map.get(ts) + 1);
                    map.put(sign, map.get(sign) + 1);
                    while (map.get(ts) > nums.get(ts) ) {
                        String rmts = s.substring(slow, slow + step);
                        map.put(rmts, map.get(rmts) - 1);
                        slow += step;
                        map.put(sign, map.get(sign) - 1);
                    }
                    if (map.get(sign) == n) {
                        ans.add(slow);
                        String rmts = s.substring(slow, slow + step);
                        map.put(rmts, map.get(rmts) - 1);
                        slow += step;
                        map.put(sign, map.get(sign) - 1);
                    }
                    fast += step;
                } else {
                    fast += step;
                    slow = fast;
                    if (map.get(sign) == 0) continue;
                    for(String key : map.keySet()){
                        map.put(key, 0);
                    }
                }
            }
        }

        return ans;
    }
}
